package com.cuz.daileetcode;

import com.cuz.daileetcode.utils.ArrayUtils;


public class Day30 {


    /****
     * 数组中重复的数字
     * 在长度n的数组中所有数字都在0~n-1的范围内，在数组中某些数字是重复的
     * 但不知道几个数组重复了，也不知道重复了几次，照数数组中任意一个重复的数字
     *
     * 1.排序 后遍历数组 加入下表i的数不等于i 那么这个数就是重复的
     * 因为【在长度n的数组中所有数字都在0~n-1的范围内】
     * 不重复的例子 0 1 2 3 4
     * 假如重复了 0 1 3 3 3 4 4 4 第一个不等于num[i]!=i的就是重复的数
     *
     * 时间复杂度排序=》O（NLog（N））
     *
     * 2.hashMap =》时间 O（N） 空间O（N）
     *
     * 3，遍历的同时进行移动 时间O（N） 空间O（1）
     */

    public static int findRepeat(int[] nums) {
        for (int index = 0; index < nums.length; index++) {
            int curValue = nums[index];
            //当前数的值等于 下标， 说明在正确的位置上 继续即可
            if (curValue == index) {
                continue;
            }
            // 如果当前数 等于 它应该在的位置上的数 说明重复了
            if (curValue == nums[curValue]) {
                return curValue;
            } else {
                //否则回到自己应该在的位置
                ArrayUtils.swap(nums, curValue, index);
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {0, 1, 2, 3, 4, 4, 4};
        System.out.println(findRepeat(nums));
    }
}
